package com.github.yangyishe.p100;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 22. 括号生成
 * https://leetcode.cn/problems/generate-parentheses/description/?envType=study-plan-v2&envId=top-interview-150
 *
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 *
 *
 *
 * 示例 1：
 *
 * 输入：n = 3
 * 输出：["((()))","(()())","(())()","()(())","()()()"]
 * 示例 2：
 *
 * 输入：n = 1
 * 输出：["()"]
 *
 *
 * 提示：
 *
 * 1 <= n <= 8
 */
public class Problem22 {
    public static void main(String[] args) {
        int n=1;

        Problem22 problem22 = new Problem22();
        List<String> strings = problem22.generateParenthesis(n);
        System.out.println(strings);

    }

    /**
     * 思路:
     * 括号本身的前后判断,使用stack比较合适
     * 而获取集合的方法, 可考虑使用回溯
     *
     * @param n
     * @return
     */
    public List<String> generateParenthesis(int n) {
        char[] tmp=new char[n*2];

        iterate(0,n,0,tmp,0);

        return resultList;
    }

    private List<String> resultList=new ArrayList<>();


    private void iterate(int index,int n,int leftCount,char[] tmp,int maxLeft){
        if(index==tmp.length){
            resultList.add(new String(tmp));
            return;
        }
        // 优化: 提前回溯.如果括号数量曾经达到最大值, 则直接返回
        if(maxLeft<n){
            tmp[index]='(';
            iterate(index+1,n,leftCount+1,tmp,maxLeft+1);
        }
        if(leftCount>0){
            tmp[index]=')';
            iterate(index+1,n,leftCount-1,tmp,maxLeft);
        }

    }
}
